export {}
class LNode {
  prev: LNode | null;
  next: LNode | null;
  value: { key: number; value: number };
  constructor(
    value: { key: number; value: number },
    prev: LNode | null,
    next: LNode | null
  ) {
    this.prev = prev;
    this.next = next;
    this.value = value;
  }
}
/**
 * https://leetcode-cn.com/problems/lru-cache/
 * LRU缓存机制
 */
class LRUCache {
  private capicity: number;
  // 双向链表的头
  private first: LNode;
  // 双向链表的尾
  private last: LNode | null;

  // 当前容量
  private size: number = 0;

  // 映射表
  keyToNode: Record<number, LNode>;

  constructor(capicity = 10) {
    // 默认容量是
    this.capicity = capicity;

    this.keyToNode = {};

    // 初始化双向链表
    this.first = new LNode({ key: -1, value: -1 }, null, null); // 虚拟头节点
    this.last = null;
  }

  /**
   * 获取key
   * @param key
   */
  get(key: number) {
    const n = this.keyToNode[key];
    if (n === undefined) return -1;

    // 将该节点移动到最后
    this.moveLast(n!);

    return n.value.value;
  }

  /**
   * 放入值
   * @param key
   * @param value
   */
  put(key: number, value: number) {
    const node = this.keyToNode[key];
    let nNode: LNode | null = null;
    if (node !== undefined) {
      // 修改
      node.value.value = value;
      nNode = node;
      // 移动节点到最后
      this.moveLast(node);
    } else {
      // 新增
      if (this.last === null) {
        // 首次添加
        nNode = new LNode({ key, value }, this.first, null);
        this.last = nNode;
        this.first.next = nNode;
      } else {
        // 插入到最后
        // 判断是否达到容量了
        if (this.size === this.capicity) {
          // 已经达到容量了, 清除头节点
          this.pruneEntry();
        }

        // 放到尾部
        nNode = new LNode({ key, value }, null, null);
        this.putLast(nNode);
      }
      // 容量+1
      this.size++;
    }
    // 放入map中
    this.keyToNode[key] = nNode!;
  }

  // 将节点移动到最后
  private moveLast(node: LNode) {
    // 该节点已经是尾节点了, 不处理
    if (node.next === null) return;
    // 前一个节点
    const prev = node.prev!;
    // 下一个节点
    const next = node.next;

    // 1. 删除该节点
    prev.next = next;
    next.prev = prev;

    // 2. 将该节点放到尾部
    this.putLast(node);
  }

  /**
   * 将节点放到尾部
   * @param node
   */
  private putLast(node: LNode) {
    // 获取尾节点
    const last = this.last;
    node.prev = last;
    node.next = null; // 尾节点的next为空
    if (last !== null) {
      last.next = node;
    } else {
      // 首次添加
      this.first.next = node;
    }

    // 更改最后的节点指向
    this.last = node;
  }

  /**
   * 清除头节点
   */
  private pruneEntry() {
    const first = this.first.next;
    // 首节点不为空
    if (first !== null) {
      const next = first.next;
      if (next !== null) {
        // 下一个节点不为空, 删除节点即可
        this.first.next = next;
        next.prev = this.first;
      } else {
        // 下一个节点为空, 说明链表只有一个节点, 清空头和尾节点
        this.first.next = null;
        this.last = null;
      }
      // 长度减1
      this.size--;
      delete this.keyToNode[first.value.key];
    }
    // 如果为空, 不处理
  }
}

// 数组的方式
class LRUCache2 {
  private capicity: number;
  private keys: number[];
  private values: Record<number, number>;
  constructor(capicity = 10) {
    // 默认容量是
    this.capicity = capicity;

    // 初始化keys和values
    this.keys = [];
    this.values = {};
  }

  /**
   * 查找key
   * @param key
   * @returns
   */
  private find(key: number) {
    return this.keys.indexOf(key);
  }

  /**
   * 删除key
   * @param key
   */
  private delKey(key: number) {
    const keyI = this.find(key);
    // 删除这个key
    keyI > -1 && this.keys.splice(keyI, 1);
  }

  /**
   * 获取key
   * @param key
   */
  get(key: number) {
    // 查找key
    const keyI = this.find(key);
    if (keyI > -1) {
      // 存在该值
      const val = this.values[key];

      // 删除老的key
      this.delKey(key);

      // 保持最新的key
      this.keys.push(key);
      return val;
    } else {
      return keyI;
    }
  }

  /**
   *  清除头节点
   */
  pruneEntry() {
    const key = this.keys.shift()!;
    // 删除对应的值
    delete this.values[key];
  }

  /**
   * 放入值
   * @param key
   * @param value
   */
  put(key: number, value: number) {
    // 1. 判断是不是修改的
    const keyI = this.find(key);

    const keys = this.keys;
    if (keyI > -1) {
      // 修改的
      // 1. 删除该key, value重新添加
      this.delKey(key);
    } else {
      // 新增的

      // 判断有没有达到缓存数量
      if (this.capicity === keys.length) {
        // 达到了缓存的数量, 删除掉头key, 头key就是最近未使用的
        this.pruneEntry();
      }
    }
    keys.push(key); // 保持最新的key
    this.values[key] = value;
  }
}

const lru = new LRUCache(2);

lru.put(2, 1);
lru.put(2, 2);
console.log(lru.keyToNode);

// lru.put(1, 1);
// lru.put(2, 2);
// console.log(lru.get(1));
// lru.put(3, 3);
// console.log(lru.get(2));
// lru.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
// console.log(lru.get(1)); // 返回 -1 (未找到)
// console.log(lru.get(3)); // 返回 3
// console.log(lru.get(4)); // 返回 4
